package com.leetcode.demo;

/**
 * @author 王溪源
 * @ClassName: Question70
 * @Description: 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
 *
 * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 *
 * 注意：给定 n 是一个正整数。
 *
 * 输入： 3
 * 输出： 3
 * 解释： 有三种方法可以爬到楼顶。
 * 1.  1 阶 + 1 阶 + 1 阶
 * 2.  1 阶 + 2 阶
 * 3.  2 阶 + 1 阶
 * @Date 2021/8/29 22:54
 *
 * 数学知识 排列组合
 **/
public class Question70 {
    public static int climbStairs(int n) {
        int count = 0;
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n/2; j++) {
                // x + 2y
                if((i + j * 2) == n){
                    if(i==0 || j == 0){
                        count++;
                    }else{
                        // 计算C(step,j)
                        int step = i + j;
                        for (int k = step - 1; k > i; k--) {
                            step *= k;
                        }
                        int num = 1;
                        for (int k = 1; k <= j; k++) {
                            num *= k;
                        }
                        count += step / num;
                    }
                }
            }
        }
        return count;
    }

    /**
    * 观察结果发现是斐波拉西数
    */
    public static int fibo(int n){
        if(n == 1 || n == 0){
            return 1;
        }else{
            return fibo (n - 1) + fibo (n - 2);
        }
    }

    /**
    * @Description: 动态规划
    */
    public static int fibo2(int n){
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    public static void main(String[] args) {
        System.out.println (fibo2 (35));
        System.out.println (climbStairs (2));
        System.out.println (climbStairs (3));
        /**
        * 1 + 1 + 1 + 1
         * 1 + 2 + 1
         * 1 + 1 + 2
         * 2 + 1 + 1
         * 2 + 2
        */
        System.out.println (climbStairs (4));
        /**
         * 1 + 1 + 1 + 1 + 1
         * 1 + 2 + 1 + 1
         * 1 + 2 + 2
         * 1 + 1 + 2 + 1
         * 1 + 1 + 1 + 2
         * 2 + 1 + 1 + 1
         * 2 + 2 + 1
         * 2 + 1 + 2
         */
        System.out.println (climbStairs (5));
        /**
         * 1 + 1 + 1 + 1 + 1 + 1 x = 6 y = 0
         * 1 + 2 + 1 + 1 + 1 x+2y--> x=4 y =1 4+1=5
         * 1 + 1 + 2 + 1 + 1
         * 1 + 1 + 1 + 2 + 1
         * 1 + 1 + 1 + 1 + 2
         * 2 + 1 + 1 + 1 + 1
         * 1 + 2 + 2 + 1 x=2 y =2
         * 1 + 1 + 2 + 2
         * 1 + 2 + 1 + 2
         * 2 + 2 + 1 + 1
         * 2 + 1 + 2 + 1
         * 2 + 1 + 1 + 2
         * 2 + 2 + 2 y =3
         *
         */
        System.out.println (climbStairs (6));
        System.out.println (climbStairs (7));
    }
}
